package ljl.alg.jianzhioffer.round3.easy;

import java.util.BitSet;

public class _62_lastRemaining {

    /**
     * 应该先分析复杂度。
     * */
    class okButTimeout {
        public int lastRemaining(int n, int m) {
            BitSet b = new BitSet();
            b.set(0, n);
            int i = -1;
            int j = 0;
            int remaining = n;
            while (true) {
                i++;
                if (i == n)
                    i = 0;
                if (!b.get(i))
                    continue;
                j++;
                if (j % m == 0) {
                    b.clear(i);
                    remaining--;
                    if (remaining == 1) {
                        return b.nextSetBit(0);
                    }
                }
            }
        }
    }

    class lufei {
        public int lastRemaining(int n, int m) {
            int res = 0;
            for (int i = 2; i <= n; i++) {
                res = (res + m) % i;
            }
            return res;
        }
    }

}
